#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_set>
#include<bits/stdc++.h>
#define fi first
#define se second
#define SIZE(x) ((int)x.size())
#define out(x) cerr<<#x<<" = "<<(x)<<endl;
#define MP(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
#define VI vector<int>
#define VVI vector< vector<int> >
#define VL vector<ll>
#define VVL vector<VL >
#define VC vector<char>
#define PI pair<int,int>
#define PL pair<ll,ll>
#define EPS 0.0000001


inline int lson(int x){return x<<1;}
inline int rson(int x){return (x<<1)|1;}

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

template<typename T> 
inline void read(T &x){
	x=0;T f=1;char ch;
	do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
	do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

//#define INF 5340172838076674L
#define INF 1000000000
#define MOD 998244353

struct {
	int from,to,next;
	ll val;
}edg[10000];

int esum=0;
int n,m;
int head[3005];
ll h[3005];
ll inf;

void add(int a,int b,int c){
	++esum;
	edg[esum].next=head[a];
	head[a]=esum;
	edg[esum].from=a;
	edg[esum].to=b;
	edg[esum].val=c;
}

bool SPFA(){
	bool res=true;
	h[0]=0;
	for(int i=0;i<=n;i++){
		for(int j=1;j<=esum;j++){
			if(h[edg[j].from]!=inf&&h[edg[j].from]+edg[j].val<h[edg[j].to]){
				h[edg[j].to]=h[edg[j].from]+edg[j].val;
				if(i==n)res=false;
			}
		}
	}
	return res;
}

struct node{
	ll dis,id;
	bool operator<(const node &x)const{
		return dis>x.dis;
	}
};

ll dis[3005][3005];
void dji(int x){
	priority_queue<node> pq;
	dis[x][x]=0;
	pq.push({0,x});
	while(!pq.empty()){
		auto tmp=pq.top();pq.pop();
		if(tmp.dis>dis[x][tmp.id])continue;
		for(int i=head[tmp.id];i;i=edg[i].next){
			auto id=edg[i].to;
			if(dis[x][id]>dis[x][tmp.id]+edg[i].val){
				dis[x][id]=dis[x][tmp.id]+edg[i].val;
				pq.push({dis[x][id],id});
			}
		}
	}
}

//P5905
int main(){
    #ifdef BUG
    freopen("a.in","r",stdin);
    #endif
	memset(edg,0,sizeof edg);
	memset(head,0,sizeof head);
	memset(h,0x1f,sizeof h);
	memset(dis,0x1f,sizeof dis);
	memset(&inf,0x1f,sizeof inf);

	n=read();m=read();
	int a,b,c;
	for(int i=1;i<=n;i++)add(0,i,0);
	for(int i=0;i<m;i++){
		a=read();b=read();c=read();
		add(a,b,c);
	}
	if(!SPFA()){
		printf("-1\n");
		return 0;
	}
	for(int i=n+1;i<=esum;i++)edg[i].val+=h[edg[i].from]-h[edg[i].to];
	for(int i=1;i<=n;i++){
		dji(i);
		ll res=0;
		for(int j=1;j<=n;j++){
			if(dis[i][j]==inf)res+=j*1000000000LL;
			else res+=j*(dis[i][j]+h[j]-h[i]);
		}
		printf("%lld\n",res);
	}
}
